package com.hl.algor_data_struct.sort;

import java.util.Arrays;

/**
 * Created by 31464 on 2021/10/27.
 *
 * 堆排序基本思想：
 * 1） 将排序序列构造成一个大顶堆（或者小顶堆）【升序用大顶堆，降序用小顶堆】
 * 2） 此时，整个序列的最大值就是堆顶的根节点
 * 3） 将其与末尾元素进行交换，此时末尾元素就是最大值
 * 4） 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复，就可得到一个有序数组
 *
 * 可看到在构建大顶堆的过程中，元素个数逐渐减少，最后就得到一个有序序列了
 *
 */
public class HeapSort {

    public static void main(String[] args) {
        //升序：采用大顶堆
        int[] arr={4,6,8,5,9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int arr[]){

        //1) 这个循环会将所有数据都变成一个大顶堆
        //里面adjustHeap只是局部的一个大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }

        //2) 将对顶元素与末尾元素进行交换，将最大元素放到数组末端
        //3) 重新调整结构，时期满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行，直到有序
        for(int i=arr.length-1;i>0;i--){
            int temp=arr[i];
            arr[i]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,i);
        }


    }

    /**
     * 将一个数组（二叉树），转换为大顶堆
     * @param arr  待调整数据组
     * @param i  表示非叶子节点在数组中的索引
     * @param length  表示对多少个元素继续调整，length是逐渐减少的
     */
    public static void adjustHeap(int arr[] ,int i,int length){
        int temp=arr[i];//先去除当前元素的值，保存在临时变量中
        //开始调整
        // k= i*2+1 是i节点的左子节点 i*2+2 是i节点的右子节点
        for(int k=i*2+1;k<length ; k=k*2+1){
            //k+1<length表示没有叶子节点了
            //arr[k]<arr[k+1] 左子节点的数据小于右子节点的数据，则使用右子节点的数据和父节点数据进行交换
            if(k+1<length && arr[k]<arr[k+1]){
                k++;// k 指针指向右子节点
            }

            //如果子节点数据大于父节点数据
            if(arr[k] > temp){
                arr[i]=arr[k];   //把子节点的数据赋值给父节点
                i=k;   //指正交换,循环比较
            }else{
                break;
            }
            //当for结束后，我们已经将以i为父节点树的最大值，放在了最顶部（不是整棵树，只是局部的）
            arr[i]=temp;
        }

    }




}
